package 优先算法.前缀和.和为k的子数组;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/subarray-sum-equals-k/description/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] arr = {1,1,1};
        System.out.println(so.subarraySum(arr, 2));
    }
}
class Solution {
    public int subarraySum(int[] nums, int k) {
        //前缀和+哈希表
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        map.put(0,1);
        int sum = 0 , rel = 0;
        for(int num : nums) {
            sum+=num;//保存当前的前缀和
            rel+=map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);//更新/添加当前前缀和的value
        }
        return rel;
    }
}